Wheel graph

Wheel graph
Several examples of wheel graphs
Vertices	n
Edges	2(n − 1)
Diameter	2 if n>4 1 if n=4
Girth	3
Chromatic number	3 if n is odd 4 if n is even
Spectrum	$\{2 \cos(2 k \pi / n)^1; k = 1, \ldots, n - 1\}$ $\cup \{1 \pm \sqrt{1 %2B n}\}$
Properties	Hamiltonian Self-dual Planar
Notation	W_n

In the mathematical discipline of graph theory, a wheel graph W_n is a graph with n vertices, formed by connecting a single vertex to all vertices of an (n-1)-cycle. The numerical notation for wheels is used inconsistently in the literature: some authors instead use n to refer to the length of the cycle, so that their W_n is the graph we denote W_n+1.^[1] A wheel graph can also be defined as the 1-skeleton of an (n-1)-gonal pyramid.

Wheel graphs are planar graphs, and as such have a unique planar embedding. More specifically, every wheel graph is a Halin graph. They are self-dual: the planar dual of any wheel graph is an isomorphic graph. Any maximal planar graph, other than K₄ = W₄, contains as a subgraph either W₅ or W₆.

There is always a Hamiltonian cycle in the wheel graph and there are $n^2-3n%2B3$ cycles in W_n (sequence A002061 in OEIS).

The 7 cycles of the wheel graph W₄.

For odd values of n, W_n is a perfect graph with chromatic number 3: the vertices of the cycle can be given two colors, and the center vertex given a third color. For even n, W_n has chromatic number 4, and (when n ≥ 6) is not perfect. W₇ is the only wheel graph that is a unit distance graph in the Euclidean plane.^[2]

The chromatic polynomial of the wheel graph W_n is :

$P_{W_n}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2)).$

In matroid theory, two particularly important special classes of matroids are the wheel matroids and the whirl matroids, both derived from wheel graphs. The k-wheel matroid is the cycle matroid of a wheel W_k+1, while the k-whirl matroid is derived from the k-wheel by considering the outer cycle of the wheel, as well as all of its spanning trees, to be independent.

The wheel W₆ supplied a counterexample to a conjecture of Paul Erdős on Ramsey theory: he had conjectured that the complete graph has the smallest Ramsey number among all graphs with the same chromatic number, but Faudree and McKay (1993) showed W₆ has Ramsey number 17 while the complete graph with the same chromatic number, K₄, has Ramsey number 18.^[3] That is, for every 17-vertex graph G, either G or its complement contains W₆ as a subgraph, while neither the 17-vertex Paley graph nor its complement contains a copy of K₄.

References

^ Weisstein, Eric W., "Wheel Graph" from MathWorld.
^ Buckley, Fred; Harary, Frank (1988), "On the euclidean dimension of a wheel", Graphs and Combinatorics 4 (1): 23–30, doi:10.1007/BF01864150 .
^ Faudree, Ralph J.; McKay, Brendan D. (1993), "A conjecture of Erdős and the Ramsey number r(W₆)", J. Combinatorial Math. and Combinatorial Comput. 13: 23–31, http://cs.anu.edu.au/people/Brendan.McKay/papers/wheels.ps.gz .